//给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。 
//
// 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。 
//
// 你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。 
//
// 
//
// 示例 1: 
//
// 
//输入: [3,2,1,5,6,4], k = 2
//输出: 5
// 
//
// 示例 2: 
//
// 
//输入: [3,2,3,1,2,4,5,5,6], k = 4
//输出: 4 
//
// 
//
// 提示： 
//
// 
// 1 <= k <= nums.length <= 10⁵ 
// -10⁴ <= nums[i] <= 10⁴ 
// 
//
// Related Topics 数组 分治 快速选择 排序 堆（优先队列） 👍 2285 👎 0


package LeetCode.editor.cn;

import java.util.Arrays;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Random;

/**
 * @author ldltd
 * @date 2023-09-11 23:06:56
 * @description 215.数组中的第K个最大元素
 */
public class KthLargestElementInAnArray{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new KthLargestElementInAnArray().new Solution();
		 int[] array = {3,2,3,1,2,4,5,5,6};
		 System.out.println(solution.findKthLargest(array,4));
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
	public int findKthLargest(int[] nums, int k) {
/*		//不对头
		// 将 int[] 数组转换为 List<Integer>
		List<Integer> list = Arrays.stream(nums)
				.boxed()
				.collect(Collectors.toList());
		// 去重并排序
		List<Integer> distinctSorted = list.stream()
//				.distinct()
				.sorted((a, b) -> b.compareTo(a))
				.collect(Collectors.toList());
		return distinctSorted.get(k - 1);*/
		/*排序后返回*/
		Arrays.sort(nums);
		return nums[nums.length - k];
	}
	/*手写快排*/
	public int findKthLargest1 ( int[] nums, int k){
		return quickSort(nums,0,nums.length-1,k);
	}
	int quickSort(int []nums,int l ,int r,int k) {
		if (l == r) return nums[l];
		int m = nums[l], i = l - 1, j = r + 1;
		while (i < j) {
			while (nums[++i] > m) ;
			while (nums[--j] < m) ;
			if (i < j) {
				int t = nums[i];
				nums[i] = nums[j];
				nums[j] = t;
			}
		}
		int sl=j-l+1;
		if(k<=sl) return quickSort(nums,l,j,k);
		return quickSort(nums,j+1,r,k-sl);
	}
	//带随机数的快排
	public int findKthLargest6(int[] nums, int k) {
		return quickSelect(nums, 0, nums.length - 1, nums.length - k);
	}
	private int quickSelect(int[] nums, int left, int right, int target) {
		int index = partition(nums, left, right);
		if (index == target) {
			return nums[index];
		} else {
			return index > target ?
					quickSelect(nums, left, index - 1, target) :
					quickSelect(nums, index + 1, right, target);
		}
	}
	//升序排序
	private int partition(int[] nums, int left, int right) {
		swap(nums, left, left + new Random().nextInt(right - left + 1));
		int pivot = nums[left];
		while (left < right) {
			while (left < right && nums[right] > pivot) {
				right--;
			}
			if (left < right) {
				nums[left++] = nums[right];
			}
			while (left < right && nums[left] < pivot) {
				left++;
			}
			if (left < right) {
				nums[right--] = nums[left];
			}
		}
		nums[left] = pivot;
		return left;
	}
	/*堆(优先队列)排序*/
		public int findKthLargest2 ( int[] nums, int k){
			PriorityQueue<Integer> q = new PriorityQueue<>(k, Collections.reverseOrder());
			for (int i = 0; i < nums.length; i++) {
				q.offer(nums[i]);
			}
			for (int i = 1; i < k; i++) {
				q.poll();
			}
			return q.poll();
		}
		//`````````````````````````````````````````````
		/*手写堆排序*/
		public int findKthLargest3(int[] nums,int k){
			int n = nums.length;
			buildMaxHeap(nums,n);
			//堆排序,依次出堆
			for (int i = n-1; i >=nums.length-k+1 ; i--) {
				//最后一个位置和第一个位置交换相当于删除根堆顶
				swap(nums,0,i);
				--n;
				//重新构建
				maxHeapify(nums,0,n);
			}
			return nums[0];
		}
		/*构建大根堆*/
		private void buildMaxHeap(int[] nums,int size){
			//从后往前建堆，则最后一个元素是n-1.他的父节点就是n/2-1 或者(n-1-1)/2
			//这里写size/2也不影响
			for (int i = size/2; i >=0	 ; i--) {
				maxHeapify(nums,i,size);
			}
		}
		/*调整，这里是从上往下调整*/
		private void maxHeapify(int [] nums,int i,int size){
			//已知父结点为 i，求孩子结点的下标：左孩子 = 2i + 1，右孩子 = 2i + 2
			//已知孩子结点为 i，求父节点的下标：( i - 1 ) / 2
				int l=i*2+1,r=i*2+2,largest=i;
				if(l<size&&nums[l]>nums[largest]){
					largest=l;
				}
				if(r<size&&nums[r]>nums[largest]){
					largest=r;
				}
				if(largest!=i){
					swap(nums,i,largest);
					maxHeapify(nums,largest,size);
				}
		}
		/*交换*/
		private void swap(int [] nums,int i,int j){
			int t=nums[i];
			nums[i]=nums[j];
			nums[j]=t;
		}
		//``````````````````````````
	/*计数排序*/
		public int findKthLargest4(int[] nums, int k) {
			int [] slots=new int[20001];
			//因为题目里面有负数这里加上10000
			for (int num : nums) {
				slots[num+10000]++;
			}
			for (int i =slots.length-1; i >=0 ; i--) {
				//倒序开始，每次减去计数， 比如倒数是 ……344555，
				//则k=4的数就是 4-(5的计数3）=1，  再减去4的计数2=-1，返回4
				k-=slots[i];
				if(k<=0){
					return i-10000;
				}
			}
			return 0;
		}
		/*小根堆，建立一个k大小的小堆，依次加入堆中，
		满的时候就出堆，这样最小的n-k个数就都出去了，此时堆顶就是第k个大的数*/
	public int findKthLargest5(int[] nums, int k) {
			int [] arr=new int[k];
		for (int i = 0; i < k; i++) {
			arr[i]=nums[i];
		}
			buildMin(arr,k);
		for (int i = k; i < nums.length; i++) {
			if(nums[i]>arr[0]){
				arr[0]=nums[i];
				heapify(arr,0,k);
			}
		}
		return arr[0];

	}
	private void buildMin(int[] nums,int size){
		for (int i = size/2-1; i>=0; i--) {
				heapify(nums,i,size);
		}
	}
	private void heapify(int[] nums,int i,int size){
		while (true){
			int l=i*2+1,r=i*2+2,mn=i;
			if(l<size&&nums[mn]>nums[l]) mn=l;
			if(r<size&&nums[mn]>nums[r]) mn=r;
			if(mn==i)break;
			swap(nums,i,mn);
			i=mn;
		}

	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
